//给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入: [1,2,3,null,5,null,4]
//输出: [1,3,4]
// 
//
// 示例 2: 
//
// 
//输入: [1,null,3]
//输出: [1,3]
// 
//
// 示例 3: 
//
// 
//输入: []
//输出: []
// 
//
// 
//
// 提示: 
//
// 
// 二叉树的节点个数的范围是 [0,100] 
// 
// -100 <= Node.val <= 100 
// 
//
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 921 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2023-08-17 12:39:13
 * @description 199.二叉树的右视图
 */
public class BinaryTreeRightSideView{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new BinaryTreeRightSideView().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

  //Definition for a binary tree node.
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
          this.left = left;
         this.right = right;
     }
  }

class Solution {
         /*层次遍历*/
    public List<Integer> rightSideView1(TreeNode root) {
        List<Integer>res=new ArrayList<>();
        if(root==null) return res;
        Queue<TreeNode> q= new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()){
            int t=q.size();
            while (t>0){
                TreeNode poll = q.poll();
                if(poll.left!=null){
                    q.offer(poll.left);
                }
                if(poll.right!=null){
                    q.offer(poll.right);
                }
                t--;
                if(t==0) res.add(poll.val);
            }
        }
        return  res;
    }
/*dfs
* 先访问右节点*/
    public List<Integer> rightSideView(TreeNode root) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int max_dep=-1;
        Deque<TreeNode> nS=new LinkedList<>();
        Deque<Integer>dS=new LinkedList<>();
        nS.push(root);
        dS.push(0);
        while (!nS.isEmpty()){
            TreeNode poll = nS.poll();
            int dep=dS.pollFirst();
            if(poll!=null){
                //维护最大深度
                max_dep=Math.max(dep,max_dep);
                //如果不存在对应的深度，插入
                if(!map.containsKey(dep)){
                    map.put(dep,poll.val);
                }
                nS.push(poll.left);
                nS.push(poll.right);
                dS.push(dep+1);
                dS.push(dep+1);
            }
        }
        List<Integer>res=new ArrayList<>();
        for (int d=0;d<=max_dep;d++){
            res.add(map.get(d));
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
